/**
 * 二叉树的最小深度
 *
 * 给定一个二叉树，找出其最小深度。
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * 说明：叶子节点是指没有子节点的节点。
 *
 * 示例 1：
 * 输入：root = [3,9,20,null,null,15,7]
 * 输出：2
 *
 * 示例 2：
 * 输入：root = [2,null,3,null,4,null,5,null,6]
 * 输出：5
 *
 * 提示：
 * 树中节点数的范围在 [0, 105] 内
 * -1000 <= Node.val <= 1000
 */

/**
 * 这题要求得最小深度, 我肯会用到
 * Math.min, 这里我们用的 时候,
 * 肯定是有可能会遇到, 有一个节点的
 * 左边或者右边为空节点, 然后, 我们
 * 会选他的最小节点, 这个时候, 我们选的
 * 一定会是 0, 但是我们要求的是叶子节点
 * 这个节点不是肯定是要舍去的, 所以我们在
 * 写条件的时候要注意一下
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(H) H 为树高
 */

public class Main {
    public int minDepth(TreeNode root) {

        // 空节点高度为 0
        if (root == null) {
            return 0;
        }

        // 要是为叶子节点, 那么高度就是 1
        if (root.left == null && root.right == null) {
            return 1;
        }

        int left = minDepth(root.left);
        int right = minDepth(root.right);

        // 这里要是有一个为空, 说明他的高度是 0, 那么我们直接将它加进去就可以了
        if (root.left == null || root.right == null) {
            return left + right + 1;
        }

        // 进入下一个节点, 高度加 1
        return Math.min(left, right) + 1;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}